package q828_uniqueLetterString;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution_1 {
    /*
    对于任意一个字符，如果它在字符串只出现一次，那么我们标记它某次出现的位置为idx 上次出现为i 下次出现为j
    那么在 i -> j 这一段中符合包含该字符且只有一个该字符的字符串有 (idx - i) * (j - idx)种可能
    因此我们记录每一个字符出现的位置的list 并加入 -1 和 length 两个边界位置
    基于此即可计算所有的可能
     */
    public int uniqueLetterString(String s) {
        Map<Character, List<Integer>> index = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!index.containsKey(c)) {
                index.put(c, new ArrayList<>());
                index.get(c).add(-1);
            }
            index.get(c).add(i);
        }
        int res = 0;
        for (Map.Entry<Character, List<Integer>> entry : index.entrySet()) {
            List<Integer> arr = entry.getValue();
            arr.add(s.length());
            for (int i = 1; i < arr.size() - 1; i++) {
                res += (arr.get(i) - arr.get(i - 1)) * (arr.get(i + 1) - arr.get(i));
            }
        }
        return res;
    }

}
